package lcr;

public class Test0026 {
}

class Solution0026_1 {
    public void reorderList(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode temp = slow.next;
        slow.next = null;
        slow= temp;

        slow = reverseList(slow);

        while (slow != null){
            temp = slow.next;
            slow.next = head.next;
            head.next = slow;

            head=slow.next;
            slow=temp;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode ans = new ListNode();
        while (head!=null){
            ListNode temp = head.next;
            head.next=ans.next;
            ans.next=head;
            head=temp;
        }
        return ans.next;
    }
}
